package com.duing.tree;

import java.util.LinkedList;
import java.util.Queue;

public class MergeTree {

    public static void main(String[] args) {
        Integer[] arr = new Integer[]{1, 3, 2, 5, 7, null, null, 9};
        Integer[] arr1 = new Integer[]{2, 1, 3, null, 4, null, 7, null, null, 10};
        TreeNode node1 = createByArray(arr, 0);
        TreeNode node2 = createByArray(arr1, 0);

        //TreeNode node3 = mergeTrees(node1, node2);
        TreeNode node4 = mergeTrees1(node1, node2);
        System.out.println();
    }

    // 使用先序遍历的递归方式   中序和后序的递归同理
    // 同样可以使用 非递归方式
    public static TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        // 如果一颗树为空  则返回另一颗树  都为空按照情况1返回
        if (root1 == null) return root2;
        if (root2 == null) return root1;
        // 合并后的树
        TreeNode merged = new TreeNode(root1.val + root2.val);
        merged.left = mergeTrees(root1.left, root2.left);
        merged.right = mergeTrees(root1.right, root2.right);
        return merged;
    }

    // 广度优先遍历
    // Queue {1}
    //       {2,3}
    //       {3,4,5}
    //       {4,5,6,7}
    //       {5,6,7,8,9}

    // 层级遍历
    // {1}{2,3}{4,5,6,7}{8,9}

    // 合并二叉树的 广度优先遍历   每颗树都需要一个队列
    // queue1 {1}
    //        {3,2}
    //        {5}
    // queue2 {2}
    //        {1,3}
    //        {4,7}
    // queue  {3}
    //        {4,5}
    //        {5,4,7}
    public static TreeNode mergeTrees1(TreeNode root1, TreeNode root2) {
        // 入参有效性校验
        if (root1 == null) return root2;
        if (root2 == null) return root1;

        TreeNode merged = new TreeNode(root1.val + root2.val);
        Queue<TreeNode> queue1 = new LinkedList<>();
        Queue<TreeNode> queue2 = new LinkedList<>();
        // 合并树使用的队列
        Queue<TreeNode> queue = new LinkedList<>();
        queue1.offer(root1);
        queue2.offer(root2);
        queue.offer(merged);
        while (true) {
            if (queue1.isEmpty() && queue2.isEmpty()) {
                break;
            }

            TreeNode node1 = queue1.poll();
            TreeNode node2 = queue2.poll();
            TreeNode node = queue.poll();

            TreeNode left1 = node1.left;
            TreeNode left2 = node2.left;
            if (left1 != null && left2 != null) {
                // 在两个节点都不为空时 加和处理
                TreeNode left = new TreeNode(left1.val + left2.val);
                node.left = left;
                queue.offer(left);
                queue1.offer(left1);
                queue2.offer(left2);
            } else if (left1 != null && left2 == null) {
                // 当一侧子树为空时  挂载不为空的子树  同时也不需要存储到队列中
                // 因为不论此子树有多少节点  都不需要再遍历了
                node.left = left1;
            } else if (left2 != null && left1 == null) {
                node.left = left2;
            }

            TreeNode right1 = node1.right;
            TreeNode right2 = node2.right;
            if (right1 != null && right2 != null) {
                TreeNode right = new TreeNode(right1.val + right2.val);
                node.right = right;
                queue.offer(right);
                queue1.offer(right1);
                queue2.offer(right2);
            } else if (right1 != null && right2 == null) {
                node.right = right1;
            } else if (right2 != null && right1 == null) {
                node.right = right2;
            }

        }
        return merged;
    }


    // 根据数组和索引位置  关联出左右子树
    public static TreeNode createByArray(Integer[] array, int index) {
        // 递归的出口
        if (index >= array.length) return null;
        if (array[index] == null) return null;

        // 递归的规律
        TreeNode node = new TreeNode(array[index]);
        node.left = createByArray(array, 2 * index + 1);
        node.right = createByArray(array, 2 * index + 2);
        return node;
    }
}


// ctrl + R是批量替换
// ctrl + alt + L 是自动格式化
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}